#include "headfiles.h"

using namespace std;

vector<Interval> mergeIntervals(vector<Interval> intervals) {
    map<int, Interval> left;
    vector<Interval> output;

    // Sorted according to the start value
    for (auto it = intervals.begin(); it != intervals.end(); it++) {
        auto iit = left.find(it->start);
        if (iit == left.end()) {
            left[it->start] = *it;
        }
        else {
            if (iit->second.end < it->end) {
                left[it->start] = *it;
            }
        }
    }

    for (auto lit = left.begin(); lit != left.end();) {
        auto nit = lit;
        ++nit;
        int end = lit->second.end;
        while (nit != left.end()) {
            if (end >= nit->first) {
                if (nit->second.end > end) {
                    end = nit->second.end;
                }
                nit++;
            }
            else {
                break;
            }
        }

        Interval val;
        val.start = lit->first;
        val.end = end;
        output.push_back(val);

        lit = nit;
    }

    return output;
}
